1. Field
Embodiments of the present invention relate to an apparatus and method for planning a robot path so as to rapidly plan a smooth path of a robot using a parallel algorithm and a variable motion database.
2. Description of the Related Art
In general, a mechanical device which performs motion similar to human motion using an electrical or magnetic mechanism is called a robot. Most early robots served as manipulators used for automated or unmanned tasks in manufacturing plants or industrial robots such as transfer robots, such that they can perform dangerous tasks, simple and repeated tasks, and tasks requiring high power on behalf of a human being. In recent times, a humanoid robot, which has articulated joint structures similar to that of a human being, and which coexists with a human being so as to support human lives, residential living services, and human activity in other daily lives, has been developed.
The humanoid robot performs a given task using a manipulator which performs motion similar to those of arms or hands of a human being according to electrical and mechanical mechanisms. Most manipulators are configured by interconnecting a plurality of links. The connection part between individual links is called a joint, and motion characteristics of the manipulator are determined according to the geometric relationship between links and joints. A numerical expression of the above geometric relationship is called kinematics. Most manipulators move an end effector of the robot in a direction (goal point) along which a task is performed with kinematic characteristics.
In order to enable the manipulator to perform a given task (e.g., grasping an object), it is necessary to create the moving path of the manipulator from an initial position (start point) before the execution of the task to the final position (goal point) where the robot can grasp the object. There are a variety of Sampling Based Path Planning (SBPP) methods in which the manipulator satisfies a constraint condition such as collision avoidance so that the manipulator does not collide with an obstacle within an operation region. A representative example of an SBPP method is a Rapidly-exploring Random Tree (RRT) algorithm.
The RRT algorithm uses a shape that is randomly sampled within a Configuration Space (C-Space) in which the manipulator or the humanoid robot performs an operation. One example of the RRT algorithm extends the tree by repeating a process of selecting a node closest to the initial start point such that it searches for the moving path to the final goal point. The exemplary RRT algorithm selects a node having the smallest goal score from among the tree using the distance from the goal point to the end effector and a goal function composed of direction-vector functions, such that it can extend the tree.
However, the conventional RRT algorithm has to search the entire space when generating the path, such that a long period of time is needed to plan the final path. In addition, a large number of calculations are needed for implementation of high dimension, so that a long period of time is needed to plan the final path.